% Ejercicio "De notación polaca inversa a notación infija"
\subsection*{\fbox{\theejercicio} - De notaci\'on polaca inversa a notaci\'on infija}

Se desea construir mediante LEX y YACC un traductor de notacion polaca inversa a notacion infija. Las expresiones en notaci\'on polaca inversa utilizan los cuatro operadores b\'asicos, n\'umeros enteros, n\'umeros reales e identificadores alfanum\'ericos. Los operadores y operandos est\'an separados por comas y terminados en punto y coma. Por ejemplo, el siguiente fichero contiene cuatro expresiones en notaci\'on polaca inversa:

\begin{verbatim}
1,2,+;
1,2.5,3,4.7,*,+,+,5,+; 
(int) alfa, (int) beta, (float) gamma, -, - ;
1,2,*,3.5,-,4.5,+,(int) alfa,/;
\end{verbatim}

que una vez traducidas deben dar lugar a las expresiones infijas:

\begin{verbatim}
(1+2);
((1+(2.5+(3*4.7)))+5);
(alfa-(beta-gamma));
((((1*2)-3.5)+4.5)/alfa);
\end{verbatim}

\begin{enumerate}[1)]
\item  Suponiendo que solo se utilizan n\'umeros enteros y operadores, implementar mediante LEX y YACC una gram\'atica que compruebe que los ficheros fuente son correctos desde el punto de vista l\'exico y sint\'actico.
\item Implementar el traductor utilizando solamente n\'umeros enteros y operadores aritm\'eticos.
\item Implementar el traductor usando n\'umeros enteros y n\'umeros reales (sin exponente) y determinar en funci\'on de los argumentos, cu\'al es el tipo de resultado. Se supone que la operaci\'on de divisi\'on da siempre como resultado un numero real, aunque sean enteros sus argumentos. El resultado de las dem\'as operaciones depender\'a del tipo de los argumentos, siguiendo las convenciones habituales para promoci\'on de enteros a reales en caso necesario.
\item A\~nadir identificadores, cuyo tipo debe ser declarado precediendo al nombre de la variable, seg\'un muestra el ejemplo.
\item Implementar un contador del n\'umero de expresiones correctas que hay en el fichero y que han podido.
\end{enumerate}

% Solución del ejercicio
\subsubsection*{SOLUCI\'ON}

\underline{ESPECIFICACI\'ON LEX}:

\begin{verbatim}
%{
#include "main.h"
#include "y.tab.h"
%}
%%
\(int\)               {
                         yylval.atr.tipo = TIPOENTERO; 
                         return TIPO; 
                      }
\(float\)             {
                          yylval.atr.tipo = TIPOREAL; 
                          return TIPO; 
                      }
[a-zA-Z][a-zA-Z0-9]+  {
                          strcpy (yylval.atr.cod , yytext);
                          return IDENT;
                      }
[-+]?[1-9][0-9]*      {
                          strcpy (yylval.atr.cod , yytext);
                          yylval.atr.tipo = TIPOENTERO; 
                          return NUMERO;
                      }
[-+]?(0|[1-9][0-9]*)\.[0-9]+ {
                         strcpy (yylval.atr.cod , yytext);
                         yylval.atr.tipo = TIPOREAL; 
                         return NUMERO;
                      }
[-+*/,;]              {
                            return yytext[0];
                      }
[ \t]+                { ; }
\n                    {
                        numlinea++;
                      }
                      {
                        char *st = (char*) malloc(100);
                        sprintf(st,"Caracter inesperado: %s",yytext);
                        yyerror(st);
                      }
%%
\end{verbatim}

\underline{ESPECIFICACI\'ON YACC}:

\begin{verbatim}
%{
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include "main.h"
%}

%union {
   struct { 
      int tipo;
      char cod[100];
   } atr;
   int contador;
}

%type  <atr>       Expresion 
%type  <contador>  ListaExpresiones

%token <atr>       NUMERO
%token <atr>       IDENT
%token <atr>       TIPO

%%

Axioma: ListaExpresiones 
      {
         printf ("Se han traducido %d expresiones correctas\n", $1);
      }
      ;

ListaExpresiones: ListaExpresiones Expresion `;'
                  {
                      if ($2.tipo == TIPOENTERO) {
                          printf("%s; (int)\n",$2.cod);
                          $$ = $1 + 1;
                      } else if ($2.tipo == TIPOREAL) {
                          printf("%s; (float)\n",$2.cod);
                          $$ = $1 + 1;
                      } else {
                          printf("ERROR1 EN LA EXPRESION\n");
                      }
                  }
                | ListaExpresiones error `;'
                      {
                          printf("ERROR2 EN LA EXPRESION\n");
                      }
                | /* vacio */
                  {
                      $$ = 0;
                  }
                ;

Expresion:   NUMERO
             {
                 strcpy($$.cod, $1.cod);
                 $$.tipo = $1.tipo; 
             }
         |   TIPO IDENT
             {
                 strcpy($$.cod, $2.cod);
                 $$.tipo = $1.tipo;
             }
         |   Expresion `,' Expresion `,' `+'
             {
                 sprintf($$.cod, "(%s + %s)", $1.cod,$3.cod);
                 if ($1.tipo == TIPOENTERO && $3.tipo == TIPOENTERO) {
                     $$.tipo = TIPOENTERO;
                 } else {
                     $$.tipo = TIPOREAL; 
                 } 
             }
         |   Expresion `,' Expresion `,' `-'
             {
                 sprintf($$.cod, "(%s - %s)", $1.cod,$3.cod);
                 if ($1.tipo == TIPOENTERO && $3.tipo == TIPOENTERO) {
                     $$.tipo = TIPOENTERO;
                 } else {
                     $$.tipo = TIPOREAL; 
                 } 
             }
         |   Expresion `,' Expresion `,' `*'
             {
                 sprintf($$.cod, "(%s * %s)", $1.cod,$3.cod);
                 if ($1.tipo == TIPOENTERO && $3.tipo == TIPOENTERO) {
                     $$.tipo = TIPOENTERO;
                 } else {
                     $$.tipo = TIPOREAL; 
                 } 
             }
         |   Expresion `,' Expresion `,' `/'
             {
                 sprintf($$.cod, "(%s / %s)", $1.cod,$3.cod);
                 $$.tipo = TIPOREAL;
             }
         ;
\end{verbatim}

\underline{FICHERO main.h}:

\begin{verbatim}
#define yywrap() 1

extern char *nombreprograma;
extern char *nombrefichero;
extern int numlinea;
extern void yyerror(char *);

#define TIPOERROR 0
#define TIPOENTERO 1
#define TIPOREAL 2
\end{verbatim}

\underline{FICHERO main.c}:

\begin{verbatim}
#include <stdio.h>

extern FILE *yyin;
extern FILE *yyout;


char *nombreprograma = NULL;
char *nombrefichero = NULL;
int numlinea=1;

extern void iniTipos();

/******************/
/* main           */
/******************/
main (int argc, char *argv[])
{
    void cerrarficheros ();
    int abrirficheros ();
    nombreprograma = argv[0];
    if (abrirficheros (argc,argv) == 1) {
        yyparse();
    }
    cerrarficheros();
    return (1);
}

/***************************************/
/* abrirficheros                       */
/* abre los ficheros de entrada/salida */
/* devuelve 0 en caso de error         */
/***************************************/
abrirficheros (int argc, char **argv)
{
  if (argc > 3) { 
     printf ("Demasiados parametros.\n");
     return 0; 
  }
  if (argc > 1) { 
     nombrefichero = argv[1];
     yyin=fopen (argv[1], "r");
  }
  if (yyin == NULL) { 
     printf ("Fichero no encontrado.\n");
     return 0; 
  }
  if (argc > 2) { 
     yyout=fopen (argv[2], "w");
  }
  return 1;
}

/*****************************************/
/* cerrarficheros                        */
/* cierra los ficheros de entrada/salida */
/*****************************************/
void cerrarficheros () {fclose (yyin); fclose (yyout); return; }

/*******************************************************/
/* yyerror                                             */
/*******************************************************/
void yyerror(char *s)
{
    fprintf(stderr,"%s %s(%d): %s \n",
            nombreprograma, nombrefichero, numlinea, s);
}
\end{verbatim}

\underline{FICHERO Makefile}:

\begin{verbatim}
# Compilador

CC = gcc

# Flags

CFLAGS = -g

# Ficheros

PROG = npi

HDRS = main.h

CSRCS = main.c

SRCS = $(CSRCS) \
       lex.yy.c \
       y.tab.c

OBJS = main.o \
       lex.yy.o \
       y.tab.o

.c.o:
       $(CC) -c $(CFLAGS) $*.c

#

$(PROG): $(OBJS)
     $(CC) $(CFLAGS) $(OBJS) -o $(PROG)

# Dependencias de los ficheros C

$(OBJS): $(HDRS)

# Dependencies de los ficheros de LEX y YACC

lex.yy.c: $(PROG).l y.tab.h
    lex $(PROG).l

y.tab.c y.tab.h: $(PROG).y
    yacc -d $(PROG).y

borrar:
    rm $(PROG) *.o y.tab.c y.tab.h lex.yy.c y.output
\end{verbatim}

